#pragma once
#include <iostream>
template <class T>
class Link
{
public:
    T value;
    explicit Link(const T &v, Link *p = nullptr, Link *s = nullptr)
        : value(v), prev(p), succ(s) {}
    Link *insert(Link *n);
    Link *add(Link *n);
    Link *add_ordered(Link *n);
    Link *erase();
    Link *find(const T &v);
    const Link *find(const T &v) const;
    Link *advance(int n);
    const Link *advance(int n) const;
    Link *next() const { return succ; }
    Link *previous() const { return prev; }

private:
    Link *prev;
    Link *succ;
};
template <class T>
Link<T> *Link<T>::insert(Link *n)
{
    if (n == nullptr)
        return this;
    n->succ = this;
    if (prev)
        prev->succ = n;
    n->prev = prev;
    prev = n;
    return n;
}
template <class T>
Link<T> *Link<T>::add(Link *n)
{
    if (n == nullptr)
    {
        return this;
    }
    if (succ)
        succ->prev = n;
    n->succ = succ;
    n->prev = this;
    succ = n;
    return n;
}
template <class T>
Link<T> *Link<T>::add_ordered(Link<T> *n)
{
    if (n == nullptr)
    {
        return this;
    }
    if (n->value < value)
    {
        return insert(n);
    }
    else
    {
        Link<T> *p = this;
        while (p->next() && (p->next()->value <= n->value))
        {
            p = p->next();
        }
        return p->add(n);
    }
}
template <class T>
Link<T> *Link<T>::find(const T &v)
{
    return const_cast<Link<T> *>(static_cast<const Link *>(this)->find(v));
}
template <class T>
Link<T> *Link<T>::erase()
{
    if (succ)
        succ->prev = prev;
    if (prev)
        prev->succ = succ;
    return succ;
}
template <class T>
const Link<T> *Link<T>::find(const T &v) const
{
    const Link<T> *p = this;
    while (p)
    {
        if (p->value == v)
            return p;
        p = p->succ;
    }
    return nullptr;
}
template <class T>
Link<T> *Link<T>::advance(int n)
{
    return const_cast<Link<T> *>(static_cast<const Link<T> *>(this)->advance(n));
}
template <class T>
const Link<T> *Link<T>::advance(int n) const
{
    const Link<T> *p = this;
    if (n > 0)
    {
        while (n--)
        {
            if (p->succ == nullptr)
                return nullptr;
            p = p->succ;
        }
    }
    else if (n < 0)
    {
        while (n++)
        {
            if (p->prev == nullptr)
                return nullptr;
            p = p->prev;
        }
    }
    return p;
}
template <class T>
std::ostream &operator<<(std::ostream &os, Link<T> *p)
{
    for (; p; p = p->next())
    {
        os << p->value << std::endl;
    }
    return os;
}
template <class T>
void destroy(Link<T> *p)
{
    while (p)
    {
        Link<T> *next = p->next();
        delete p;
        p = next;
    }
}